/*
试题 基础练习 十六进制转八进制
资源限制
内存限制：512.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s
问题描述
　　给定n个十六进制正整数，输出它们对应的八进制数。

输入格式
　　输入的第一行为一个正整数n （1<=n<=10）。
　　接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。

输出格式
　　输出n行，每行为输入对应的八进制正整数。

　　【注意】
　　输入的十六进制数不会有前导0，比如012A。
　　输出的八进制数也不能有前导0。

样例输入
　　2
　　39
　　123ABC

样例输出
　　71
　　4435274

　　【提示】
　　先将十六进制数转换成某进制数，再由某进制数转换成八进制。
*/


/*
	本题思路:
	十六进制转八进制我们可以先把十六进制转二进制, 再由二进制转到八进制
	
	题目给定的是一个字符串, 我们很多人都会想到把字符串先转换为数值;
	但这就错了, 因为十六进制字符串可能会很长, 导致转换成的数值非常大, 所以我们存储的始终要是字符串;
	(注意: 蓝桥杯不支持C++11, 即stoi, to_string, auto等不能使用)
	并且, 题目要求输出对应八进制整数, 不是让我们真的将十六进制字符串转换为真正的八进制整数,
	因为当字符串长度过长时, 没有一个整形类型能表示, 所以输出的时候我们也要按字符串来输出.
*/

/*--------------------------------------------- 写法一 -----------------------------------------------------*/

#include<iostream>
#include<vector>
#include<list>
#include<string>
using namespace std;

int main()
{
	int n;
	cin >> n;
	// 存放 n 个八进制字符串
	// 用 list 存放每个字符方便头插
	// !!这里要注意, 模板嵌套模板的时候, 中间要加空格!!
	vector< list<char> > Oct;
	for (int i = 0; i<n; i++){
		string hex_num;
		string binary_num;
		cin >> hex_num;
		for (int j = 0; j < hex_num.size(); j++){
			switch (hex_num[j]){
			case '0':
				binary_num.append("0000");
				break;
			case '1':
				binary_num.append("0001");
				break;
			case '2':
				binary_num.append("0010");
				break;
			case '3':
				binary_num.append("0011");
				break;
			case '4':
				binary_num.append("0100");
				break;
			case '5':
				binary_num.append("0101");
				break;
			case '6':
				binary_num.append("0110");
				break;
			case '7':
				binary_num.append("0111");
				break;
			case '8':
				binary_num.append("1000");
				break;
			case '9':
				binary_num.append("1001");
				break;
			case 'a':
			case 'A':
				binary_num.append("1010");
				break;
			case 'b':
			case 'B':
				binary_num.append("1011");
				break;
			case 'c':
			case 'C':
				binary_num.append("1100");
				break;
			case 'd':
			case 'D':
				binary_num.append("1101");
				break;
			case 'e':
			case 'E':
				binary_num.append("1110");
				break;
			case 'f':
			case 'F':
				binary_num.append("1111");
				break;
			default:
				break;
			}
		}
		
		//不考虑前导0
		//start指向的位置是二进制序列最前面的 1
		int start = 0;
		while (binary_num[start] == '0')
			start++;

		// 表示一个八进制字符串序列
		// 用list方便头插
		list<char> oct_num;
		// 从后往前遍历, 每三个二进制转换为一个八进制
		for (int j = binary_num.size() - 3; j >= start; j -= 3){
			oct_num.push_front((binary_num[j] - '0') * 4 + (binary_num[j + 1] - '0') * 2 + (binary_num[j + 2] - '0') + '0');
		}
		// 二进制序列 0/1 的个数可能不满足 3 倍数
		// 如果余数是1, 则二进制序列最前面还有一个1
		// 如果余数是2, 则二进制序列最前面要么是10, 要么是11
		// 10 八进制是 2, 11 八进制是 3
		if ((binary_num.size() - start) % 3 == 1)
			oct_num.push_front('1');
		else if ((binary_num.size() - start) % 3 == 2){
			if (binary_num[start + 1] == '0')
				oct_num.push_front('2');
			else
				oct_num.push_front('3');
		}

		Oct.push_back(oct_num);
	}
	for (int i = 0; i < n; i++){
		// list 不支持下标访问, 用迭代器比较合适
		list<char>::iterator it = Oct[i].begin();
		while (it != Oct[i].end()){
			cout << *it;
			it++;	//别忘了++
		}
		cout << endl;
	}
	return 0;
}

/*------------------------------------------------------------------------------------------------------------*/

/*---------------------------------------------- 写法一 ------------------------------------------------------*/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
using namespace std;

char hex_num[100001];
char binary_num[400004];
char oct_num[10][133334];
long length[10];

void hex_to_binary(long size)
{
	int i = size-1;
	int j = 400003;
	while (i>=0){
		if (hex_num[i] == '0'){
			binary_num[j - 3] = '0'; binary_num[j - 2] = '0'; binary_num[j - 1] = '0'; binary_num[j] = '0';
		}
		else if (hex_num[i] == '1'){
			binary_num[j - 3] = '0'; binary_num[j - 2] = '0'; binary_num[j - 1] = '0'; binary_num[j] = '1';
		}
		else if (hex_num[i] == '2'){
			binary_num[j - 3] = '0'; binary_num[j - 2] = '0'; binary_num[j - 1] = '1'; binary_num[j] = '0';
		}
		else if (hex_num[i] == '3'){
			binary_num[j - 3] = '0'; binary_num[j - 2] = '0'; binary_num[j - 1] = '1'; binary_num[j] = '1';
		}
		else if (hex_num[i] == '4'){
			binary_num[j - 3] = '0'; binary_num[j - 2] = '1'; binary_num[j - 1] = '0'; binary_num[j] = '0';
		}
		else if (hex_num[i] == '5'){
			binary_num[j - 3] = '0'; binary_num[j - 2] = '1'; binary_num[j - 1] = '0'; binary_num[j] = '1';
		}
		else if (hex_num[i] == '6'){
			binary_num[j - 3] = '0'; binary_num[j - 2] = '1'; binary_num[j - 1] = '1'; binary_num[j] = '0';
		}
		else if (hex_num[i] == '7'){
			binary_num[j - 3] = '0'; binary_num[j - 2] = '1'; binary_num[j - 1] = '1'; binary_num[j] = '1';
		}
		else if (hex_num[i] == '8'){
			binary_num[j - 3] = '1'; binary_num[j - 2] = '0'; binary_num[j - 1] = '0'; binary_num[j] = '0';
		}
		else if (hex_num[i] == '9'){
			binary_num[j - 3] = '1'; binary_num[j - 2] = '0'; binary_num[j - 1] = '0'; binary_num[j] = '1';
		}
		else if (hex_num[i] == 'a' || hex_num[i] == 'A'){
			binary_num[j - 3] = '1'; binary_num[j - 2] = '0'; binary_num[j - 1] = '1'; binary_num[j] = '0';
		}
		else if (hex_num[i] == 'b' || hex_num[i] == 'B'){
			binary_num[j - 3] = '1'; binary_num[j - 2] = '0'; binary_num[j - 1] = '1'; binary_num[j] = '1';
		}
		else if (hex_num[i] == 'c' || hex_num[i] == 'C'){
			binary_num[j - 3] = '1'; binary_num[j - 2] = '1'; binary_num[j - 1] = '0'; binary_num[j] = '0';
		}
		else if (hex_num[i] == 'd' || hex_num[i] == 'D'){
			binary_num[j - 3] = '1'; binary_num[j - 2] = '1'; binary_num[j - 1] = '0'; binary_num[j] = '1';
		}
		else if (hex_num[i] == 'e' || hex_num[i] == 'E'){
			binary_num[j - 3] = '1'; binary_num[j - 2] = '1'; binary_num[j - 1] = '1'; binary_num[j] = '0';
		}
		else if (hex_num[i] == 'f' || hex_num[i] == 'F'){
			binary_num[j - 3] = '1'; binary_num[j - 2] = '1'; binary_num[j - 1] = '1'; binary_num[j] = '1';
		}
		j -= 4;
		i--;
	}
}

long binary_to_oct(long size,int index)
{
	long beg = 400003;
	long end = 400004 - 4 * size;
	while (binary_num[end] == '0')
		end++;
	long j = 133333;
	for (long i = beg-2; i >= end; i -= 3){
		oct_num[index][j] = (binary_num[i] - '0') * 4 + (binary_num[i + 1] - '0') * 2 + (binary_num[i + 2] - '0') + '0';
		j--;
	}
	if ((beg - end + 1) % 3 == 1){
		oct_num[index][j] = '1';
		return 133334 - j;
	}
	else if ((beg - end + 1) % 3 == 2){
		if (binary_num[end + 1] == '0')
			oct_num[index][j] = '2';
		else
			oct_num[index][j] = '3';
		return 133334 - j;
	}
	return 133334 - j - 1;
}
int main()
{
	int n;
	cin >> n;
	int k = 0;
	while (k < n){
		scanf("%s", hex_num);
		long len = strlen(hex_num);
		hex_to_binary(len);
		length[k]=binary_to_oct(len, k);
		k++;
	}
	for (int i = 0; i < n; i++){
		for (int j = 133334 - length[i]; j < 133334; j++)
			cout << oct_num[i][j];
		cout << endl;
	}
	return 0;
}








